#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[startRow][startColumn] = 1;
        int ret = 0, mod = 1e9 + 7;
        for (int p = 0; p < maxMove; p++) {
            vector<vector<int>> newdp(m, vector<int>(n, 0));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] > 0) {
                        for (int k = 0; k < 4; k++) {
                            int a = i + dx[k], b = j + dy[k];
                            if (a >= 0 && a < m && b >= 0 && b < n) {
                                newdp[a][b] = (newdp[a][b] + dp[i][j]) % mod;
                            }
                            else
                                ret = (ret + dp[i][j]) % mod;
                        }
                    }
                }
            }
            dp = newdp;
        }
        return ret;
    }
};